1. Field of the Invention
The present invention is directed to providing a general set of subdivision rules, which provides more control over the subdivision process. More particularly, the present invention provides a set of subdivision rules which blend approximating spline based schemes with interpolatory schemes, and allows any number of refinements to be performed in a single operation. The present invention also works for both triangles and quadrilaterals in the same mesh. The result is a subdivision scheme, which provides a more natural and desirable effect than existing rules.
2. Description of the Related Art
Subdivision surfaces are a popular modeling tool used in computer graphics. This is in part because these surfaces combine the benefits of both polygonal and NURBS (Non-Uniform Rational B-Spline) modeling. Subdivision surfaces, like NURBS, allow users to model smooth surfaces by manipulating a small set of control vertices. A subdivision scheme defines how a base mesh is iteratively divided until a “smooth” surface is produced.
Current subdivision rules, such as the Catmull-Clark algorithm, can result in a surface that is smaller than the base mesh. For example, see FIG. 1, which illustrates a prior art method of subdividing a base mesh 100. The base mesh 100 is divided into a first subdivided surface 102, the first subdivided surface 102 is further divided into a second subdivided surface 104. The second subdivided surface 104 can be continuously divided, resulting in an approximation of a limit curve 106. Note how the limit curve 106 is smaller than the original base mesh 100. This “distortion” is a result of the subdivision and smoothing schemes used, and may not be what the user intended. Further, current subdivision schemes and smoothing schemes may produce unwanted effects.
Another limitation of the prior art is that a base shape, for example a square, can only be subdivided into a number of smaller pieces that is a power of 4. For example, a square can be subdivided into a 2×2 grid of 4 pieces, a 4×4 grid of 16 pieces, etc. However, the prior art subdivision schemes do not allow for a square to be subdivided into an arbitrary number of pieces, for example a 5×5 grid of 25 pieces.
The prior art also does not allow to mix triangles and quadrilaterals in the same base mesh. For example, the Catmull-Clark method works only with quadrilaterals, the Butterfly method only with triangles. What was generally done was to perform a first ad hoc subdivision step to transform general objects into triangles or quads only. The problem with this is that the resulting shape is then generally not very pleasing.
Therefore, what is needed, is a more flexible approach of creating improved subdivision surfaces.